package com.dyz.leetcode._06_binarySearch;

public class _1095_findInMountainArray {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        //1.找到峰顶的元素
        int peakIndex = searchPeakIndex(mountainArr);

        //2。在前半段使用二分查找
        int index = binarySearchFrontPart(mountainArr, 0, peakIndex, target);
        if(index!=-1){
            return index;
        }
        //3.后半部分二分查找

        return  binarySearchLatterPart(mountainArr, peakIndex, mountainArr.length()-1, target);
    }

    // 2. 在前半部分应用二分查找算法查找目标值（思路 2 实现）
    private int binarySearchFrontPart(MountainArray mountainArr, int left, int peakIndex, int target) {
        while (left < peakIndex) {
            int mid = left + (peakIndex - left) / 2;
            if (target > mountainArr.get(mid)) {
                left = mid + 1;
            } else {
                peakIndex = mid;
            }
        }
        if (mountainArr.get(left) == target) {return left;}
        return -1;
    }

    private int searchPeakIndex(MountainArray mountainArr) {
        int left = 0;
        int right = mountainArr.length() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    // 3. 在后半部分应用二分查找算法查找目标值（思路 2 实现）
    private int binarySearchLatterPart(MountainArray mountainArr, int peakIndex, int right, int target) {
        while (peakIndex < right) {
            int mid = peakIndex + (right - peakIndex) / 2;
            if (target < mountainArr.get(mid)) {
                peakIndex = mid + 1;
            } else {
                right = mid;
            }
        }
        if (mountainArr.get(peakIndex) == target) {return peakIndex;}
        return -1;
    }

    public interface MountainArray {
        public int get(int index);
        public int length();
    }
}
